package com.bupt.interview;

import java.util.ArrayList;
import java.util.Stack;

import com.bupt.datastruct.TreeNode;

public class Solution1 {
	/**
	 * 在数组中找一个元素，元素之前的数都小于这个元素，这个数之后的元素都大于元素
	 * @param num
	 * @return
	 */
	public ArrayList<Integer> findNum(int num[]){
		ArrayList<Integer> res = new ArrayList<Integer>();
		if(num.length <= 2){
			return res;
		}
		int preMax[] = new int[num.length];
		int postMin[] = new int[num.length];
		preMax[0] = num[0];
		for(int i = 1;i< num.length;i++){
			preMax[i] = preMax[i-1] > num[i-1]?preMax[i-1]:num[i-1]; 
		}
		postMin[num.length-1] = num[num.length-1];
		for(int j = num.length-2; j>=0;j--){
			postMin[j] = postMin[j+1]>num[j+1]?num[j+1]:postMin[j+1];
		}
		
		for(int k = 1; k<num.length-1;k++){
			if(preMax[k] < num[k] && num[k] < postMin[k]){
				res.add(k);
			}
		}
		return res;
	}
	/**
	 * 排序字符串数组，O(N)复杂度解法，O(1)空间复杂度
	 * @param arr
	 */
    public void sortCharArray(char [] arr) {
    	int big = 0,small = 0, num = 0;
    	for(int i = 0;i<arr.length;i++){
    		if(arr[i] >= '0' &&  arr[i] <= '9'){
    			num++;
    		}else if(arr[i] >= 'A' && arr[i] <= 'Z') {
    			big++;
    		}else if(arr[i] >= 'a' && arr[i] <= 'z'){
    			small++;
    		}else {
    			return;
    		}
    	}
    	int bigIndex = 0,smallIndex = big , numIndex = big + small;
    	while (bigIndex < big  ) {
    		//为大写字母时
    		if(arr[bigIndex]  >= 'A' && arr[bigIndex] <= 'Z') {
    			bigIndex++;
    		//为小数时
    		}else if(arr[bigIndex] >= '0' && arr[bigIndex] <= '9'){
    			if(arr[numIndex] >= '0' && arr[bigIndex] <= '9'){
    				numIndex++;
    			}else {
    				char temp = arr[numIndex];
    				arr[bigIndex] = arr[numIndex];
    				arr[numIndex] = temp;
    				numIndex++;
    				if(temp >= 'A' && temp <= 'Z'){
    					bigIndex++;
    				}
    			}
    		//为小写字母时	
    		}else {
    			if(arr[smallIndex] >= 'a' && arr[smallIndex] <='z'){
    				smallIndex++;
    			}else {
    				char temp = arr[smallIndex];
    				arr[smallIndex] = arr[bigIndex];
    				arr[bigIndex] = temp;
    				smallIndex++;
    				if(temp >= 'A' && temp <='Z'){
    					bigIndex++;
    				}
    			}
    		}
    	}
    	//排序已经完成！
    	if(smallIndex >= big+small || numIndex >= arr.length) return;
    	else {
    		while(smallIndex < big + small || numIndex < arr.length){
    			if(arr[smallIndex] <= '9' && arr[bigIndex] >='0'){
    				char temp = arr[smallIndex];
    				arr[smallIndex] = arr[bigIndex];
    				arr[bigIndex] = temp;
    			}
    			bigIndex++;
    			smallIndex++;
    		}
    	}
    	return;
    }
}
